package com.jeff.android.lab.algorithm;

import android.widget.TextView;

import com.jeff.android.lab.BaseFragment;
import com.jeff.android.lab.R;

import butterknife.BindView;
import butterknife.OnClick;

/*
* 快速排序
* 时间复杂度 O(NlogN)
* */
public class QuickSortFragment extends BaseFragment {

    @BindView(R.id.tv_source)
    TextView tv_source;

    @BindView(R.id.tv_result)
    TextView tv_result;

    private int[] data = {49, 38, 65, 97, 76, 13, 27};

    @Override
    protected int getRootLayout() {
        return R.layout.algorithm_fragment_quick_sort;
    }

    @Override
    protected void initView() {
        super.initView();
        print(tv_source);
    }

    @OnClick()
    public void onClick() {

    }

    @Override
    protected void initData() {
        sort(data, 0, 6);
        print(tv_result);
    }

    /*
    *
    * */
    private void sort(int arr[], int low, int high) {
        int l = low;
        int h = high;
        int povit = arr[low]; // 第一个数作为基准

        // 每次循环目的就是找到基准数的正确位置，就是基准数左侧的数都要小于等于它，右侧的数都要大于等于它
        while (l < h) {
            // 从最右边开始，直到找到比基准数小的数
            while (l < h && arr[h] >= povit) {
                h--;
            }
            if (l < h) {
                arr[l] = arr[h]; // 将从右侧开始找到的比基准数小的数赋值给索引 l 的数
                l++;
            }

            // 接着从左侧开始，直到找到比基准数大的数
            while (l < h && arr[l] <= povit) {
                l++;
            }
            if (l < h) {
                arr[h] = arr[l];// 将从左侧开始找到的比基准数大的数赋值给索引 h 的数
                h--;
            }
        }

        // 当 l==h 时，就是基准数正确的位置，进行赋值
        arr[l] = povit;

        // 将基准数左侧和右侧分别递归快速排序
        if (l - 1 > low) sort(arr, low, l - 1);
        if (h + 1 < high) sort(arr, h + 1, high);
    }


    private void print(TextView tv) {
        StringBuilder sb = new StringBuilder("");
        for (int i = 0; i < data.length; i++) {
            sb.append(data[i]);
            if (i < data.length - 1)
                sb.append(",");
        }
        tv.setText(sb.toString());
    }

}
